# -*- coding: utf-8 -*-

'''
maxheapify.py
Created on Junho de 2013
@authors: 
    Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
    Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''

"""
O algoritmo heapsort
Time Complexity of Solution:
    Melhor caso O(n log(n));
    Caso médio O(n log(n));
    Pior O(n log(n)).

Características do heapsort
    - O tempo de execução é O(n lg (n))
    - Ordenação local
    - Usa uma estrutura de dados chamada heap

A estrutura de dados heap (binário) é um array que pode ser
visto como uma árvore binária praticamente completa
    - Cada nó da árvore corresponde ao elemento do array que
      armazena o valor do nó
    - A árvore está preenchida em todos os níveis, exceto 
      talvez no nível mais baixo, que é preenchido a partir
      da esquerda

MaxHeap:
Os valores nos nós satisfazem uma propriedade de heap
- Numa heap máximo, a propriedade de heap máximo é que,
  para todo nó i diferente da raiz A[parent(i)] ≥ A[i]
  
Análise do heapsort
- A chamada a build-max-heap demora O(n)
- O procedimento max-heapify demora O(lgn) e é chamado (n − 1) vezes
- Portanto, o tempo de execução do heapsort é O(n lg (n))



Como utilizar:
 - EXEMPLO: Ordenação do array A:
 
   A = [ 16,4,10,14,7,9,3,2,8,1 ]
   print "Array: ", A 
   print "\nBuild-Max-Heap"
   mh = MaxHeap(A)
   mh.heapsort()
   print "\nSort: ", mh

RESULTADO:
Array:  [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]

Build-Max-Heap

Sort:  1, 2, 3, 4, 7, 8, 9, 10, 14, 16
>>>

"""

import math
import random

class MaxHeap(object):
    '''
    Classe onde valores nos nós satisfazem uma propriedade de heap
      - Numa heap máximo, a propriedade de heap máximo é que,
        para todo nó i diferente da raiz A[parent(i)] ≥ A[i]
    '''

    def __init__(self, A):
        ''' Constructor '''
        self.A = A
        self.heapsize = len(A)


    def left(self, i):
        ''' Nó descendente esquerdo do nó i '''
        return 2 * i + 1

    
    def right(self, i):
        ''' Nó descendente direito do nó i '''
        return 2 * i + 2

    def maxHeapify(self, i):
        '''
        Max_Heapify, tem um custo O(lg n)
        É chamada (n-1) vezes
        Manter a propriedade de max-heap
        max-heap: o valor associado ao nó é, no máximo 
                  igual ao do seu nó progenitor: 
                              A[PARENT(I) >= A[I]
            - ou seja, o valor mais elevado está armazenado no nó raiz
            - a sub-árvore associada a um nó é, não contém valores mais 
              elevados do que os do nó.
              
            :Parameters:
              - 'i': Indice i da tabela
        '''
        l = self.left(i)
        r = self.right(i)
        
        if (l < self.heapsize and self.A[l] > self.A[i]):
            largest = l
        else:
            largest = i
        if (r < self.heapsize and self.A[r] > self.A[largest]):
            largest = r 
        if (largest != i):
            self.A[i], self.A[largest] = self.A[largest], self.A[i]
            self.maxHeapify(largest)

    def buildMaxHeap(self):
        '''
        O algoritmo Build-Max-Heap constrói uma heap a partir de
        uma sequência de dados A[1, ..., n], n = len(A).
        Cada chamada desta função tem custo O(n), e é chamada 1 vez.
        '''
        for i in range(int(math.floor(self.heapsize/2)),0,-1):
            self.maxHeapify(i)


    def heapSort(self):
        '''
        Ordenação dos elementos, otida por colocação dos 
        elementos de topo da heap.
        Custo total do algoritmo HeapSort O(n lg n)
        '''
        self.buildMaxHeap()
        for i in range(self.heapsize -1, 0, -1):
            self.A[0], self.A[i] = self.A[i], self.A[0]
            self.heapsize = self.heapsize - 1
            self.maxHeapify(0)

    def heapsort(self):
        '''
        Algoritmo não-recursivo.
        '''
        # in pseudo-code, heapify only called once, so inline it here
        for start in range((self.heapsize - 2) /2, -1, -1):
            self.siftDown( start, self.heapsize - 1)
        # Swap
        for end in range(self.heapsize - 1, 0, -1):
            self.A[end], self.A[0] = self.A[0], self.A[end]
            self.siftDown( 0, end - 1)

    def siftDown(self, start, end):
        '''
        Verifica se um elemento é maior do que o seu filho
        Se não os valores do elemento e o filho são trocados.
        A Função continua a verificar e a trocar até que o 
        elemento fique numa posição em que é maior do que 
        os seus filhos.
        '''
        root = start
        while True:
            child = root * 2 + 1 
            if child > end: break
            if child + 1 <= end and self.A[child] < self.A[child + 1]:
                child += 1
            if self.A[root] < self.A[child]:
                self.A[root], self.A[child] = self.A[child], self.A[root]
                root = child
            else:
                break

    def __str__(self):
        return ', '.join(map(str, self.A))



def main():

   A = [ 16,4,10,14,7,9,3,2,8,1 ]
   print "Array: ", A 
   print "\nBuild-Max-Heap"
   mh = MaxHeap(A)
   mh.heapsort()
   print "\nSort: ", mh


if __name__ == '__main__':
    main()

